package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/16 7:20 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0767 {

    public String reorganizeString(String s) {

        int length = s.length();
        int[] charFreq = new int[26];
        char[] chars = s.toCharArray();

        int maxIndex = 0;
        int maxCount = 0;
        for (int i = 0; i < chars.length; i++) {
            int charIndex = chars[i] - 'a';
            charFreq[charIndex]++;
            if (charFreq[charIndex] > maxCount) {
                maxIndex = charIndex;
                maxCount = charFreq[charIndex];
            }
        }

        if (maxCount>(length+1)/2) {
            return "";
        }

        char[] result = new char[length];

        int start = 0;
        while (charFreq[maxIndex] >= 0) {
            result[start] = (char)(maxIndex + 'a');
            charFreq[maxIndex]-- ;
            start += 2;
        }

        if (start >= length) {
            start = 1;
        }

        for (int i = 0; i < 26; i++) {
            while (charFreq[i] > 0) {
                result[start] = (char) (i + 'a');
                charFreq[i]--;
                start += 2;
                if (start >= length) {

                    start = 1;
                }
            }
        }


        return new String(result);


    }
}
